//哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’
//t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一
//本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。 
//
//
// 注意：本题相对原题稍作改动，只需返回未识别的字符数 
//
// 
//
// 示例： 
//
// 输入：
//dictionary = ["looked","just","like","her","brother"]
//sentence = "jesslookedjustliketimherbrother"
//输出： 7
//解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。
// 
//
// 提示： 
//
// 
// 0 <= len(sentence) <= 1000 
// dictionary中总字符数不超过 150000。 
// 你可以认为dictionary和sentence中只包含小写字母。 
// 
//
// Related Topics 字典树 数组 哈希表 字符串 动态规划 哈希函数 滚动哈希 👍 223 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-09-16 23:01:27
 * @description 面试题 17.13.恢复空格
 */
public class ReSpaceLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ReSpaceLcci fun=new ReSpaceLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 动态规划，dp[i]表示处理到i的时候不能识别的字符串长度数量
	//dp[0]=0,时间复杂度on2
    public int respace1(String[] dictionary, String sentence) {
        int n=sentence.length();
		if(n==0) return 0;
		Set<String> set=new HashSet<>(List.of(dictionary));
		int []dp=new int[n+1];
		for (int i = 1; i <=n; i++) {
			//初始为不认识
			dp[i]=dp[i-1]+1;
			for (int j = 0; j < i; j++) {
				if(set.contains(sentence.substring(j,i))){
					dp[i]=Math.min(dp[i],dp[j]);
				}
			}
		}
		return dp[n];
    }
	// 字典树
	public int respace2(String[] dictionary, String sentence) {
		int n = sentence.length();

		Trie root = new Trie();
		// 注意这里的字典树是反向构建的，因为要判断有没有以某个字母结尾的单词
		for (String word: dictionary) {
			root.insert(word);
		}

		int[] dp = new int[n + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		for (int i = 1; i <= n; ++i) {
			dp[i] = dp[i - 1] + 1;

			Trie curPos = root;
			for (int j = i; j >= 1; --j) {
				int t = sentence.charAt(j - 1) - 'a';
				// 如果当前位置的字母在字典树中，并且以当前位置结尾
				// 则更新dp[i]
				// 如果没有以当前结尾的，直接跳过
				if (curPos.next[t] == null) {
					break;
					// 如果以当前位置结尾，则更新dp[i]，因为是倒序插入，倒序遍历，实际上end代表的是以某个字母开头
				} else if (curPos.next[t].isEnd) {
					dp[i] = Math.min(dp[i], dp[j - 1]);
				}
				// 如果dp[i]已经为0，则跳过
				if (dp[i] == 0) {
					break;
				}
				curPos = curPos.next[t];
			}
		}
		return dp[n];
	}
}

	class Trie {
		public Trie[] next;
		public boolean isEnd;

		public Trie() {
			next = new Trie[26];
			isEnd = false;
		}

		public void insert(String s) {
			Trie curPos = this;

			for (int i = s.length() - 1; i >= 0; --i) {
				int t = s.charAt(i) - 'a';
				if (curPos.next[t] == null) {
					curPos.next[t] = new Trie();
				}
				curPos = curPos.next[t];
			}
			curPos.isEnd = true;
		}

}

	static final long P = Integer.MAX_VALUE; //大质数
	static final long BASE = 41; //进制基数
		//滚动hash,通过预计算hash值，判断子串是否在词典中
	/*
	对于子串s[j:i]，哈希计算过程：
	初始: hash = 0
	加入s[i-1]: hash = (0 * 41 + t) % P
	加入s[i-2]: hash = (hash * 41 + t) % P
	...
	加入s[j]: hash = (hash * 41 + t) % P
	每次计算在上一次的基础上
	*
	* */
	public int respace(String[] dictionary, String sentence) {
		Set<Long> hashValues = new HashSet<Long>();
		for (String word : dictionary) {
			hashValues.add(getHash(word)); // 计算每个词的哈希值并存入集合
		}

		int[] f = new int[sentence.length() + 1];
		Arrays.fill(f, sentence.length());  // 初始化为最大值

		f[0] = 0; // 空字符串的未识别字符数为0
		for (int i = 1; i <= sentence.length(); ++i) {
			f[i] = f[i - 1] + 1;  // 假设当前字符不认识
			long hashValue = 0;
			//句子中的子串：反向计算哈希（从i向前到j） 这样保证相同的字符串会产生相同的哈希值
			for (int j = i; j >= 1; --j) { // 从i向前遍历
				int t = sentence.charAt(j - 1) - 'a' + 1; // 字符映射到1-26
				hashValue = (hashValue * BASE + t) % P;  // 滚动计算哈希值
				if (hashValues.contains(hashValue)) {  // 如果哈希值在词典中
					f[i] = Math.min(f[i], f[j - 1]);   // 更新最小未识别字符数
				}
			}
		}

		return f[sentence.length()];
	}
	//哈希计算公式：hash = (hash * BASE + char_value) % P
	public long getHash(String s) {
		long hashValue = 0;
		// 词典中的词：正向计算哈希（从右向左）
		for (int i = s.length() - 1; i >= 0; --i) {
			hashValue = (hashValue * BASE + s.charAt(i) - 'a' + 1) % P;
		}
		return hashValue;
	}
//leetcode submit region end(Prohibit modification and deletion)

}
